package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/*
请编写一个方法，返回某集合的所有非空子集。
给定一个int数组A和数组的大小int n,请返回A的所有非空子集。
保证A的元素个数小于等于20，且元素互异。
各子集内部从大到小排序,子集之间字典逆序排序

 */
public class e非空子集 {
	public static void main(String[] args) {
		e非空子集 test = new e非空子集();
		int[] arr = new int[] {1, 2, 3};
		Set<Set<Integer>> res1 = test.recursion1(arr, arr.length - 1);
		System.out.println(res1);
		
		Set<Set<Integer>> res2 = test.recursion2(arr, arr.length);
		System.out.println(res2);
		
		ArrayList<ArrayList<Integer>> res3 = test.recursion3(arr, arr.length);
		System.out.println(res3);
	}
	
	/**
	 * 二进制迭代法
	 * 也称“逐步生成法”
	 * 不含空子集
	 * @param arr
	 * @param length
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> recursion3(int[] arr, int length) {
		Arrays.sort(arr);//这个步骤是为了按字典序存新子集；加上这行代码。最终结果只能是逆序
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();//声明“最终集合”
		for (int i = (int) (Math.pow(2, length) - 1); i > 0; i--) {//去除空集后，“最终集合”共有(2^length)-1个子集
			ArrayList<Integer> element = new ArrayList<Integer>();//声明每个子集；此时子集是空的
			for (int j = length - 1; j >= 0; j--) {//开始对子集填充内容；这个for循环的逻辑意义是“根据i的二进制数不同位置上的1，把arr对应位置的数字摘出来，放到一个子集中”
				/*
				填充的法则是：
					i决定着“有几个子集”
					i的二进制数(二进制数的有效长度是 = arr.length，从低位到高位)不同位置上的1表示		这个“第i个子集”含有“arr对应位置的数字”
						arr = {1,2,3}
						非空子集数 = 2^3 - 1 = 7
						假设i = 7
						那么i = (111)二进制数
						那么第i个子集是 = {3,2,1}；我这里321的顺序是有意义的
					j是为了让程序确认"i的二进制数"每一位，而产生的变量
					j即代表着“i的二进制数”向右偏移的量，也代表着arr中对应位置的索引，所以最大 = length - 1，最小 = 0
				 */
				if (((i >>> j) & 1) == 1) {
					element.add(arr[j]);
				}
			}
			res.add(element);//res存入新子集
		}
		return res;
	}
	
	/**
	 * 迭代形式
	 * 含有空子集
	 * @param arr
	 * @param length
	 * @return
	 */
	public Set<Set<Integer>> recursion2(int[] arr, int length) {// length是arr.length
		Set<Set<Integer>> res = new HashSet<Set<Integer>>();
		res.add(new HashSet<Integer>());//填入初始元素————空集
		for (int i = 0; i < length; i++) {//开始迭代，填入所有子集；
			Set<Set<Integer>> newRes = new HashSet<Set<Integer>>();//声明新“最终集合”
			newRes.addAll(res);//新“最终集合”先把老“最终集合”所有元素拷贝
			for (Set<Integer> element : res) {//再把每一个老“最终集合”的元素element进行“追加新内容使element变成新子集”的操作
				Set<Integer> cloneElement = (Set<Integer>) ((HashSet<Integer>) element).clone();
				cloneElement.add(arr[i]);//进行“追加新内容使element变成新子集”的操作
				newRes.add(cloneElement);//新“最终集合”再把每一个新子集填入
			}
			res = newRes;//覆盖
		}
		return res;
	}
	
	/**
	 * 递归形式
	 * 含有空子集
	 * 
	 * 返回的新“最终集合”，中的每个元素都是Set<Integer>，每个元素中都是Integer
	 * 不是层次非常深的树数据结构，将来的我别再去纠结了
	 * @param arr
	 * @param n
	 * @param current
	 * @return 新“最终集合”
	 */
	public Set<Set<Integer>> recursion1(int[] arr, int current) {//参数 current = arr.length - 1
		Set<Set<Integer>> newSet = new HashSet<Set<Integer>>();//先声明一个用来装子集的集合
		if (current == 0) {//这里是递归出口
			Set<Integer> nullElement = new HashSet<Integer>();//声明空集
			Set<Integer> firstElement = new HashSet<Integer>();//声明第一个子集；注意此时第一个子集还仅仅是声明，没有填入内容；第一个子集作为“最终集合”的第一个元素
			firstElement.add(arr[current]);//第一个子集填入内容
			newSet.add(nullElement);//“最终集合”填入空集
			newSet.add(firstElement);//“最终集合”填入第一个子集(有内容了)
			return newSet;//返回新“最终集合”
		}
		Set<Set<Integer>> oldSet = recursion1(arr, current - 1);//递归
		for (Set<Integer> element : oldSet) {//遍历老“最终集合”的所有元素
			newSet.add(element);//对遍历的每一个元素，先原封不动填入新“最终集合”
			Set<Integer> cloneElement = (Set<Integer>) ((HashSet) element).clone();
			cloneElement.add(arr[current]);//对遍历的每一个元素的克隆体(克隆体使用新的地址)，填入内容；这个操作就是对每个老“最终集合”的子集element进行“拼上新元素从而使element成为新子集”的操作
			newSet.add(cloneElement);//再把新子集(即填入新内容的element，在代码中是cloneElement表示)填入新“最终集合”
		}
		return newSet;//返回新“最终集合”
	}
}
